/*-------------------------------------------------------------------------
 *
 * extended_stats.c
 *	  POSTGRES extended statistics
 *
 * Generic code supporting statistics objects created via CREATE STATISTICS.
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/statistics/extended_stats.c
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/detoast.h"
#include "access/genam.h"
#include "access/htup_details.h"
#include "access/table.h"
#include "catalog/indexing.h"
#include "catalog/pg_collation.h"
#include "catalog/pg_statistic_ext.h"
#include "catalog/pg_statistic_ext_data.h"
#include "executor/executor.h"
#include "commands/defrem.h"
#include "commands/progress.h"
#include "miscadmin.h"
#include "nodes/nodeFuncs.h"
#include "optimizer/clauses.h"
#include "optimizer/optimizer.h"
#include "parser/parsetree.h"
#include "pgstat.h"
#include "postmaster/autovacuum.h"
#include "statistics/extended_stats_internal.h"
#include "statistics/statistics.h"
#include "utils/acl.h"
#include "utils/array.h"
#include "utils/attoptcache.h"
#include "utils/builtins.h"
#include "utils/datum.h"
#include "utils/fmgroids.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"
#include "utils/syscache.h"
#include "utils/typcache.h"

/*
 * 为了避免在分析期间消耗过多内存和/或在生成的 pg_statistic 行中
 * 占用过多空间，我们忽略宽度超过 WIDTH_THRESHOLD 的 varlena 数据项
 * （去除膨胀后！）。这对于 MCV 和不同值的计算是合理的，因为宽值
 * 很可能不会重复，更不可能是最常见的值。出于同样的原因，忽略宽值
 * 对我们的直方图区间边界估计不会产生太大影响。
 */
#define WIDTH_THRESHOLD  1024

/*
 * Used internally to refer to an individual statistics object, i.e.,
 * a pg_statistic_ext entry.
 */
typedef struct StatExtEntry
{
	Oid			statOid;		/* OID of pg_statistic_ext entry */
	char	   *schema;			/* statistics object's schema */
	char	   *name;			/* statistics object's name */
	Bitmapset  *columns;		/* attribute numbers covered by the object */
	List	   *types;			/* 'char' list of enabled statistics kinds */
	int			stattarget;		/* statistics target (-1 for default) */
	List	   *exprs;			/* 表达式 */
} StatExtEntry;


static List *fc_fetch_statentries_for_relation(Relation pg_statext, Oid fc_relid);
static VacAttrStats **fc_lookup_var_attr_stats(Relation fc_rel, Bitmapset *fc_attrs, List *fc_exprs,
											int fc_nvacatts, VacAttrStats **fc_vacatts);
static void fc_statext_store(Oid fc_statOid, bool fc_inh,
						  MVNDistinct *fc_ndistinct, MVDependencies *fc_dependencies,
						  MCVList *fc_mcv, Datum fc_exprs, VacAttrStats **fc_stats);
static int	fc_statext_compute_stattarget(int fc_stattarget,
									   int fc_natts, VacAttrStats **fc_stats);

/* Information needed to analyze a single simple expression. */
typedef struct AnlExprData
{
	Node	   *expr;			/* expression to analyze */
	VacAttrStats *vacattrstat;	/* statistics attrs to analyze */
} AnlExprData;

static void fc_compute_expr_stats(Relation fc_onerel, double fc_totalrows,
							   AnlExprData *fc_exprdata, int fc_nexprs,
							   HeapTuple *fc_rows, int fc_numrows);
static Datum fc_serialize_expr_stats(AnlExprData *fc_exprdata, int fc_nexprs);
static Datum fc_expr_fetch_func(VacAttrStatsP fc_stats, int fc_rownum, bool *fc_isNull);
static AnlExprData *fc_build_expr_data(List *fc_exprs, int fc_stattarget);

static StatsBuildData *fc_make_build_data(Relation fc_onerel, StatExtEntry *fc_stat,
									   int fc_numrows, HeapTuple *fc_rows,
									   VacAttrStats **fc_stats, int fc_stattarget);


/*
 * Compute requested extended stats, using the rows sampled for the plain
 * (single-column) stats.
 *
 * This fetches a list of stats types from pg_statistic_ext, computes the
 * requested stats, and serializes them back into the catalog.
 */
void BuildRelationExtStatistics(Relation fc_onerel, bool fc_inh, double fc_totalrows,
						   int fc_numrows, HeapTuple *fc_rows,
						   int fc_natts, VacAttrStats **fc_vacattrstats)
{
	Relation	pg_stext;
	ListCell   *fc_lc;
	List	   *fc_statslist;
	MemoryContext fc_cxt;
	MemoryContext fc_oldcxt;
	int64		fc_ext_cnt;

	/* Do nothing if there are no columns to analyze. */
	if (!fc_natts)
		return;

	/* the list of stats has to be allocated outside the memory context */
	pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
	fc_statslist = fc_fetch_statentries_for_relation(pg_stext, RelationGetRelid(fc_onerel));

	/* memory context for building each statistics object */
	fc_cxt = AllocSetContextCreate(CurrentMemoryContext,
								"BuildRelationExtStatistics",
								ALLOCSET_DEFAULT_SIZES);
	fc_oldcxt = MemoryContextSwitchTo(fc_cxt);

	/* report this phase */
	if (fc_statslist != NIL)
	{
		const int	fc_index[] = {
			PROGRESS_ANALYZE_PHASE,
			PROGRESS_ANALYZE_EXT_STATS_TOTAL
		};
		const int64 fc_val[] = {
			PROGRESS_ANALYZE_PHASE_COMPUTE_EXT_STATS,
			list_length(fc_statslist)
		};

		pgstat_progress_update_multi_param(2, fc_index, fc_val);
	}

	fc_ext_cnt = 0;
	foreach(fc_lc, fc_statslist)
	{
		StatExtEntry *fc_stat = (StatExtEntry *) lfirst(fc_lc);
		MVNDistinct *fc_ndistinct = NULL;
		MVDependencies *fc_dependencies = NULL;
		MCVList    *fc_mcv = NULL;
		Datum		fc_exprstats = (Datum) 0;
		VacAttrStats **fc_stats;
		ListCell   *fc_lc2;
		int			fc_stattarget;
		StatsBuildData *fc_data;

		/*
		 * Check if we can build these stats based on the column analyzed. If
		 * not, report this fact (except in autovacuum) and move on.
		 */
		fc_stats = fc_lookup_var_attr_stats(fc_onerel, fc_stat->columns, fc_stat->exprs,
									  fc_natts, fc_vacattrstats);
		if (!fc_stats)
		{
			if (!IsAutoVacuumWorkerProcess())
				ereport(WARNING,
						(errcode(ERRCODE_INVALID_OBJECT_DEFINITION),
						 errmsg("statistics object \"%s.%s\" could not be computed for relation \"%s.%s\"",
								fc_stat->schema, fc_stat->name,
								get_namespace_name(fc_onerel->rd_rel->relnamespace),
								RelationGetRelationName(fc_onerel)),
						 errtable(fc_onerel)));
			continue;
		}

		/* compute statistics target for this statistics object */
		fc_stattarget = fc_statext_compute_stattarget(fc_stat->stattarget,
												bms_num_members(fc_stat->columns),
												fc_stats);

		/*
		 * Don't rebuild statistics objects with statistics target set to 0
		 * (we just leave the existing values around, just like we do for
		 * regular per-column statistics).
		 */
		if (fc_stattarget == 0)
			continue;

		/* evaluate expressions (if the statistics object has any) */
		fc_data = fc_make_build_data(fc_onerel, fc_stat, fc_numrows, fc_rows, fc_stats, fc_stattarget);

		/* compute statistic of each requested type */
		foreach(fc_lc2, fc_stat->types)
		{
			char		fc_t = (char) lfirst_int(fc_lc2);

			if (fc_t == STATS_EXT_NDISTINCT)
				fc_ndistinct = statext_ndistinct_build(fc_totalrows, fc_data);
			else if (fc_t == STATS_EXT_DEPENDENCIES)
				fc_dependencies = statext_dependencies_build(fc_data);
			else if (fc_t == STATS_EXT_MCV)
				fc_mcv = statext_mcv_build(fc_data, fc_totalrows, fc_stattarget);
			else if (fc_t == STATS_EXT_EXPRESSIONS)
			{
				AnlExprData *fc_exprdata;
				int			fc_nexprs;

				/* should not happen, thanks to checks when defining stats */
				if (!fc_stat->exprs)
					elog(ERROR, "requested expression stats, but there are no expressions");

				fc_exprdata = fc_build_expr_data(fc_stat->exprs, fc_stattarget);
				fc_nexprs = list_length(fc_stat->exprs);

				fc_compute_expr_stats(fc_onerel, fc_totalrows,
								   fc_exprdata, fc_nexprs,
								   fc_rows, fc_numrows);

				fc_exprstats = fc_serialize_expr_stats(fc_exprdata, fc_nexprs);
			}
		}

		/* store the statistics in the catalog */
		fc_statext_store(fc_stat->statOid, fc_inh,
					  fc_ndistinct, fc_dependencies, fc_mcv, fc_exprstats, fc_stats);

		/* for reporting progress */
		pgstat_progress_update_param(PROGRESS_ANALYZE_EXT_STATS_COMPUTED,
									 ++fc_ext_cnt);

		/* free the data used for building this statistics object */
		MemoryContextReset(fc_cxt);
	}

	MemoryContextSwitchTo(fc_oldcxt);
	MemoryContextDelete(fc_cxt);

	list_free(fc_statslist);

	table_close(pg_stext, RowExclusiveLock);
}

/*
 * ComputeExtStatisticsRows
 *		Compute number of rows required by extended statistics on a table.
 *
 * Computes number of rows we need to sample to build extended statistics on a
 * table. This only looks at statistics we can actually build - for example
 * when analyzing only some of the columns, this will skip statistics objects
 * that would require additional columns.
 *
 * See statext_compute_stattarget for details about how we compute the
 * statistics target for a statistics object (from the object target,
 * attribute targets and default statistics target).
 */
int ComputeExtStatisticsRows(Relation fc_onerel,
						 int fc_natts, VacAttrStats **fc_vacattrstats)
{
	Relation	pg_stext;
	ListCell   *fc_lc;
	List	   *fc_lstats;
	MemoryContext fc_cxt;
	MemoryContext fc_oldcxt;
	int			fc_result = 0;

	/* If there are no columns to analyze, just return 0. */
	if (!fc_natts)
		return 0;

	fc_cxt = AllocSetContextCreate(CurrentMemoryContext,
								"ComputeExtStatisticsRows",
								ALLOCSET_DEFAULT_SIZES);
	fc_oldcxt = MemoryContextSwitchTo(fc_cxt);

	pg_stext = table_open(StatisticExtRelationId, RowExclusiveLock);
	fc_lstats = fc_fetch_statentries_for_relation(pg_stext, RelationGetRelid(fc_onerel));

	foreach(fc_lc, fc_lstats)
	{
		StatExtEntry *fc_stat = (StatExtEntry *) lfirst(fc_lc);
		int			fc_stattarget;
		VacAttrStats **fc_stats;
		int			fc_nattrs = bms_num_members(fc_stat->columns);

		/*
		 * Check if we can build this statistics object based on the columns
		 * analyzed. If not, ignore it (don't report anything, we'll do that
		 * during the actual build BuildRelationExtStatistics).
		 */
		fc_stats = fc_lookup_var_attr_stats(fc_onerel, fc_stat->columns, fc_stat->exprs,
									  fc_natts, fc_vacattrstats);

		if (!fc_stats)
			continue;

		/*
		 * Compute statistics target, based on what's set for the statistic
		 * object itself, and for its attributes.
		 */
		fc_stattarget = fc_statext_compute_stattarget(fc_stat->stattarget,
												fc_nattrs, fc_stats);

		/* Use the largest value for all statistics objects. */
		if (fc_stattarget > fc_result)
			fc_result = fc_stattarget;
	}

	table_close(pg_stext, RowExclusiveLock);

	MemoryContextSwitchTo(fc_oldcxt);
	MemoryContextDelete(fc_cxt);

	/* compute sample size based on the statistics target */
	return (300 * fc_result);
}

/*
 * statext_compute_stattarget
 *		compute statistics target for an extended statistic
 *
 * When computing target for extended statistics objects, we consider three
 * places where the target may be set - the statistics object itself,
 * attributes the statistics object is defined on, and then the default
 * statistics target.
 *
 * First we look at what's set for the statistics object itself, using the
 * ALTER STATISTICS ... SET STATISTICS command. If we find a valid value
 * there (i.e. not -1) we're done. Otherwise we look at targets set for any
 * of the attributes the statistic is defined on, and if there are columns
 * with defined target, we use the maximum value. We do this mostly for
 * backwards compatibility, because this is what we did before having
 * statistics target for extended statistics.
 *
 * And finally, if we still don't have a statistics target, we use the value
 * set in default_statistics_target.
 */
static int fc_statext_compute_stattarget(int fc_stattarget, int fc_nattrs, VacAttrStats **fc_stats)
{
	int			fc_i;

	/*
	 * If there's statistics target set for the statistics object, use it. It
	 * may be set to 0 which disables building of that statistic.
	 */
	if (fc_stattarget >= 0)
		return fc_stattarget;

	/*
	 * The target for the statistics object is set to -1, in which case we
	 * look at the maximum target set for any of the attributes the object is
	 * defined on.
	 */
	for (fc_i = 0; fc_i < fc_nattrs; fc_i++)
	{
		/* keep the maximum statistics target */
		if (fc_stats[fc_i]->attr->attstattarget > fc_stattarget)
			fc_stattarget = fc_stats[fc_i]->attr->attstattarget;
	}

	/*
	 * If the value is still negative (so neither the statistics object nor
	 * any of the columns have custom statistics target set), use the global
	 * default target.
	 */
	if (fc_stattarget < 0)
		fc_stattarget = default_statistics_target;

	/* As this point we should have a valid statistics target. */
	Assert((fc_stattarget >= 0) && (fc_stattarget <= 10000));

	return fc_stattarget;
}

/*
 * statext_is_kind_built
 *		Is this stat kind built in the given pg_statistic_ext_data tuple?
 */
bool statext_is_kind_built(HeapTuple fc_htup, char fc_type)
{
	AttrNumber	fc_attnum;

	switch (fc_type)
	{
		case STATS_EXT_NDISTINCT:
			fc_attnum = Anum_pg_statistic_ext_data_stxdndistinct;
			break;

		case STATS_EXT_DEPENDENCIES:
			fc_attnum = Anum_pg_statistic_ext_data_stxddependencies;
			break;

		case STATS_EXT_MCV:
			fc_attnum = Anum_pg_statistic_ext_data_stxdmcv;
			break;

		case STATS_EXT_EXPRESSIONS:
			fc_attnum = Anum_pg_statistic_ext_data_stxdexpr;
			break;

		default:
			elog(ERROR, "unexpected statistics type requested: %d", fc_type);
	}

	return !heap_attisnull(fc_htup, fc_attnum, NULL);
}

/*
 * Return a list (of StatExtEntry) of statistics objects for the given relation.
 */
static List * fc_fetch_statentries_for_relation(Relation pg_statext, Oid fc_relid)
{
	SysScanDesc fc_scan;
	ScanKeyData fc_skey;
	HeapTuple	fc_htup;
	List	   *fc_result = NIL;

	/*
	 * 准备扫描pg_statistic_ext以查找具有stxrelid = 此关系的条目。
	 */
	ScanKeyInit(&fc_skey,
				Anum_pg_statistic_ext_stxrelid,
				BTEqualStrategyNumber, F_OIDEQ,
				ObjectIdGetDatum(fc_relid));

	fc_scan = systable_beginscan(pg_statext, StatisticExtRelidIndexId, true,
							  NULL, 1, &fc_skey);

	while (HeapTupleIsValid(fc_htup = systable_getnext(fc_scan)))
	{
		StatExtEntry *fc_entry;
		Datum		fc_datum;
		bool		fc_isnull;
		int			fc_i;
		ArrayType  *fc_arr;
		char	   *fc_enabled;
		Form_pg_statistic_ext fc_staForm;
		List	   *fc_exprs = NIL;

		fc_entry = palloc0(sizeof(StatExtEntry));
		fc_staForm = (Form_pg_statistic_ext) GETSTRUCT(fc_htup);
		fc_entry->statOid = fc_staForm->oid;
		fc_entry->schema = get_namespace_name(fc_staForm->stxnamespace);
		fc_entry->name = pstrdup(NameStr(fc_staForm->stxname));
		fc_entry->stattarget = fc_staForm->stxstattarget;
		for (fc_i = 0; fc_i < fc_staForm->stxkeys.dim1; fc_i++)
		{
			fc_entry->columns = bms_add_member(fc_entry->columns,
											fc_staForm->stxkeys.values[fc_i]);
		}

		/* decode the stxkind char array into a list of chars */
		fc_datum = SysCacheGetAttr(STATEXTOID, fc_htup,
								Anum_pg_statistic_ext_stxkind, &fc_isnull);
		Assert(!fc_isnull);
		fc_arr = DatumGetArrayTypeP(fc_datum);
		if (ARR_NDIM(fc_arr) != 1 ||
			ARR_HASNULL(fc_arr) ||
			ARR_ELEMTYPE(fc_arr) != CHAROID)
			elog(ERROR, "stxkind is not a 1-D char array");
		fc_enabled = (char *) ARR_DATA_PTR(fc_arr);
		for (fc_i = 0; fc_i < ARR_DIMS(fc_arr)[0]; fc_i++)
		{
			Assert((fc_enabled[fc_i] == STATS_EXT_NDISTINCT) ||
				   (fc_enabled[fc_i] == STATS_EXT_DEPENDENCIES) ||
				   (fc_enabled[fc_i] == STATS_EXT_MCV) ||
				   (fc_enabled[fc_i] == STATS_EXT_EXPRESSIONS));
			fc_entry->types = lappend_int(fc_entry->types, (int) fc_enabled[fc_i]);
		}

		/* 解码表达式（如果有） */
		fc_datum = SysCacheGetAttr(STATEXTOID, fc_htup,
								Anum_pg_statistic_ext_stxexprs, &fc_isnull);

		if (!fc_isnull)
		{
			char	   *fc_exprsString;

			fc_exprsString = TextDatumGetCString(fc_datum);
			fc_exprs = (List *) stringToNode(fc_exprsString);

			pfree(fc_exprsString);

			/*
			 * Run the expressions through eval_const_expressions. This is not
			 * just an optimization, but is necessary, because the planner
			 * will be comparing them to similarly-processed qual clauses, and
			 * may fail to detect valid matches without this.  We must not use
			 * canonicalize_qual, however, since these aren't qual
			 * expressions.
			 */
			fc_exprs = (List *) eval_const_expressions(NULL, (Node *) fc_exprs);

			/* 也可以修复 opfuncids */
			fix_opfuncids((Node *) fc_exprs);
		}

		fc_entry->exprs = fc_exprs;

		fc_result = lappend(fc_result, fc_entry);
	}

	systable_endscan(fc_scan);

	return fc_result;
}

/*
 * examine_attribute -- pre-analysis of a single column
 *
 * Determine whether the column is analyzable; if so, create and initialize
 * a VacAttrStats struct for it.  If not, return NULL.
 */
static VacAttrStats * fc_examine_attribute(Node *fc_expr)
{
	HeapTuple	fc_typtuple;
	VacAttrStats *fc_stats;
	int			fc_i;
	bool		fc_ok;

	/*  
	 * 创建VacAttrStats结构。注意我们只有pg_attribute元组  
	 * 的固定字段的副本。  
	 */  
	fc_stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));

	/* fake the attribute */
	fc_stats->attr = (Form_pg_attribute) palloc0(ATTRIBUTE_FIXED_PART_SIZE);
	fc_stats->attr->attstattarget = -1;

	/*
	 * When analyzing an expression, believe the expression tree's type not
	 * the column datatype --- the latter might be the opckeytype storage type
	 * of the opclass, which is not interesting for our purposes.  (Note: if
	 * we did anything with non-expression statistics columns, we'd need to
	 * figure out where to get the correct type info from, but for now that's
	 * not a problem.)	It's not clear whether anyone will care about the
	 * typmod, but we store that too just in case.
	 */
	fc_stats->attrtypid = exprType(fc_expr);
	fc_stats->attrtypmod = exprTypmod(fc_expr);
	fc_stats->attrcollid = exprCollation(fc_expr);

	fc_typtuple = SearchSysCacheCopy1(TYPEOID,
								   ObjectIdGetDatum(fc_stats->attrtypid));
	if (!HeapTupleIsValid(fc_typtuple))
		elog(ERROR, "cache lookup failed for type %u", fc_stats->attrtypid);
	fc_stats->attrtype = (Form_pg_type) GETSTRUCT(fc_typtuple);

	/*
	 * We don't actually analyze individual attributes, so no need to set the
	 * memory context.
	 */
	fc_stats->anl_context = NULL;
	fc_stats->tupattnum = InvalidAttrNumber;

	/*  
	 * 描述stats->stavalues[n]元素类型的字段默认为  
	 * 正在分析的数据的类型，但特定类型的typanalyze  
	 * 函数可以在存储其他内容时更改它们。  
	 */  
	for (fc_i = 0; fc_i < STATISTIC_NUM_SLOTS; fc_i++)
	{
		fc_stats->statypid[fc_i] = fc_stats->attrtypid;
		fc_stats->statyplen[fc_i] = fc_stats->attrtype->typlen;
		fc_stats->statypbyval[fc_i] = fc_stats->attrtype->typbyval;
		fc_stats->statypalign[fc_i] = fc_stats->attrtype->typalign;
	}

	/*  
	 * 调用特定类型的typanalyze函数。如果未指定，则使用  
	 * std_typanalyze()。  
	 */  
	if (OidIsValid(fc_stats->attrtype->typanalyze))
		fc_ok = DatumGetBool(OidFunctionCall1(fc_stats->attrtype->typanalyze,
										   PointerGetDatum(fc_stats)));
	else
		fc_ok = std_typanalyze(fc_stats);

	if (!fc_ok || fc_stats->compute_stats == NULL || fc_stats->minrows <= 0)
	{
		heap_freetuple(fc_typtuple);
		pfree(fc_stats->attr);
		pfree(fc_stats);
		return NULL;
	}

	return fc_stats;
}

/*
 * examine_expression -- pre-analysis of a single expression
 *
 * Determine whether the expression is analyzable; if so, create and initialize
 * a VacAttrStats struct for it.  If not, return NULL.
 */
static VacAttrStats * fc_examine_expression(Node *fc_expr, int fc_stattarget)
{
	HeapTuple	fc_typtuple;
	VacAttrStats *fc_stats;
	int			fc_i;
	bool		fc_ok;

	Assert(fc_expr != NULL);

	/*
	 * Create the VacAttrStats struct.
	 */
	fc_stats = (VacAttrStats *) palloc0(sizeof(VacAttrStats));

	/*
	 * When analyzing an expression, believe the expression tree's type.
	 */
	fc_stats->attrtypid = exprType(fc_expr);
	fc_stats->attrtypmod = exprTypmod(fc_expr);

	/*
	 * We don't allow collation to be specified in CREATE STATISTICS, so we
	 * have to use the collation specified for the expression. It's possible
	 * to specify the collation in the expression "(col COLLATE "en_US")" in
	 * which case exprCollation() does the right thing.
	 */
	fc_stats->attrcollid = exprCollation(fc_expr);

	/*
	 * We don't have any pg_attribute for expressions, so let's fake something
	 * reasonable into attstattarget, which is the only thing std_typanalyze
	 * needs.
	 */
	fc_stats->attr = (Form_pg_attribute) palloc(ATTRIBUTE_FIXED_PART_SIZE);

	/*
	 * We can't have statistics target specified for the expression, so we
	 * could use either the default_statistics_target, or the target computed
	 * for the extended statistics. The second option seems more reasonable.
	 */
	fc_stats->attr->attstattarget = fc_stattarget;

	/* initialize some basic fields */
	fc_stats->attr->attrelid = InvalidOid;
	fc_stats->attr->attnum = InvalidAttrNumber;
	fc_stats->attr->atttypid = fc_stats->attrtypid;

	fc_typtuple = SearchSysCacheCopy1(TYPEOID,
								   ObjectIdGetDatum(fc_stats->attrtypid));
	if (!HeapTupleIsValid(fc_typtuple))
		elog(ERROR, "cache lookup failed for type %u", fc_stats->attrtypid);

	fc_stats->attrtype = (Form_pg_type) GETSTRUCT(fc_typtuple);
	fc_stats->anl_context = CurrentMemoryContext;	/* XXX should be using
												 * something else? */
	fc_stats->tupattnum = InvalidAttrNumber;

	/*  
	 * 描述stats->stavalues[n]元素类型的字段默认为  
	 * 正在分析的数据的类型，但特定类型的typanalyze  
	 * 函数可以在存储其他内容时更改它们。  
	 */  
	for (fc_i = 0; fc_i < STATISTIC_NUM_SLOTS; fc_i++)
	{
		fc_stats->statypid[fc_i] = fc_stats->attrtypid;
		fc_stats->statyplen[fc_i] = fc_stats->attrtype->typlen;
		fc_stats->statypbyval[fc_i] = fc_stats->attrtype->typbyval;
		fc_stats->statypalign[fc_i] = fc_stats->attrtype->typalign;
	}

	/*  
	 * 调用特定类型的typanalyze函数。如果未指定，则使用  
	 * std_typanalyze()。  
	 */  
	if (OidIsValid(fc_stats->attrtype->typanalyze))
		fc_ok = DatumGetBool(OidFunctionCall1(fc_stats->attrtype->typanalyze,
										   PointerGetDatum(fc_stats)));
	else
		fc_ok = std_typanalyze(fc_stats);

	if (!fc_ok || fc_stats->compute_stats == NULL || fc_stats->minrows <= 0)
	{
		heap_freetuple(fc_typtuple);
		pfree(fc_stats);
		return NULL;
	}

	return fc_stats;
}

/*
 * Using 'vacatts' of size 'nvacatts' as input data, return a newly-built
 * VacAttrStats array which includes only the items corresponding to
 * attributes indicated by 'attrs'.  If we don't have all of the per-column
 * stats available to compute the extended stats, then we return NULL to
 * indicate to the caller that the stats should not be built.
 */
static VacAttrStats **
fc_lookup_var_attr_stats(Relation fc_rel, Bitmapset *fc_attrs, List *fc_exprs,
					  int fc_nvacatts, VacAttrStats **fc_vacatts)
{
	int			fc_i = 0;
	int			fc_x = -1;
	int			fc_natts;
	VacAttrStats **fc_stats;
	ListCell   *fc_lc;

	fc_natts = bms_num_members(fc_attrs) + list_length(fc_exprs);

	fc_stats = (VacAttrStats **) palloc(fc_natts * sizeof(VacAttrStats *));

	/* lookup VacAttrStats info for the requested columns (same attnum) */
	while ((fc_x = bms_next_member(fc_attrs, fc_x)) >= 0)
	{
		int			fc_j;

		fc_stats[fc_i] = NULL;
		for (fc_j = 0; fc_j < fc_nvacatts; fc_j++)
		{
			if (fc_x == fc_vacatts[fc_j]->tupattnum)
			{
				fc_stats[fc_i] = fc_vacatts[fc_j];
				break;
			}
		}

		if (!fc_stats[fc_i])
		{
			/*
			 * Looks like stats were not gathered for one of the columns
			 * required. We'll be unable to build the extended stats without
			 * this column.
			 */
			pfree(fc_stats);
			return NULL;
		}

		/*
		 * Sanity check that the column is not dropped - stats should have
		 * been removed in this case.
		 */
		Assert(!fc_stats[fc_i]->attr->attisdropped);

		fc_i++;
	}

	/* also add info for expressions */
	foreach(fc_lc, fc_exprs)
	{
		Node	   *fc_expr = (Node *) lfirst(fc_lc);

		fc_stats[fc_i] = fc_examine_attribute(fc_expr);

		/*
		 * XXX We need tuple descriptor later, and we just grab it from
		 * stats[0]->tupDesc (see e.g. statext_mcv_build). But as coded
		 * examine_attribute does not set that, so just grab it from the first
		 * vacatts element.
		 */
		fc_stats[fc_i]->tupDesc = fc_vacatts[0]->tupDesc;

		fc_i++;
	}

	return fc_stats;
}

/*
 * statext_store
 *	Serializes the statistics and stores them into the pg_statistic_ext_data
 *	tuple.
 */
static void fc_statext_store(Oid fc_statOid, bool fc_inh,
			  MVNDistinct *fc_ndistinct, MVDependencies *fc_dependencies,
			  MCVList *fc_mcv, Datum fc_exprs, VacAttrStats **fc_stats)
{
	Relation	pg_stextdata;
	HeapTuple	fc_stup;
	Datum		fc_values[Natts_pg_statistic_ext_data];
	bool		fc_nulls[Natts_pg_statistic_ext_data];

	pg_stextdata = table_open(StatisticExtDataRelationId, RowExclusiveLock);

	memset(fc_nulls, true, sizeof(fc_nulls));
	memset(fc_values, 0, sizeof(fc_values));

	/* basic info */
	fc_values[Anum_pg_statistic_ext_data_stxoid - 1] = ObjectIdGetDatum(fc_statOid);
	fc_nulls[Anum_pg_statistic_ext_data_stxoid - 1] = false;

	fc_values[Anum_pg_statistic_ext_data_stxdinherit - 1] = BoolGetDatum(fc_inh);
	fc_nulls[Anum_pg_statistic_ext_data_stxdinherit - 1] = false;

	/*
	 * Construct a new pg_statistic_ext_data tuple, replacing the calculated
	 * stats.
	 */
	if (fc_ndistinct != NULL)
	{
		bytea	   *fc_data = statext_ndistinct_serialize(fc_ndistinct);

		fc_nulls[Anum_pg_statistic_ext_data_stxdndistinct - 1] = (fc_data == NULL);
		fc_values[Anum_pg_statistic_ext_data_stxdndistinct - 1] = PointerGetDatum(fc_data);
	}

	if (fc_dependencies != NULL)
	{
		bytea	   *fc_data = statext_dependencies_serialize(fc_dependencies);

		fc_nulls[Anum_pg_statistic_ext_data_stxddependencies - 1] = (fc_data == NULL);
		fc_values[Anum_pg_statistic_ext_data_stxddependencies - 1] = PointerGetDatum(fc_data);
	}
	if (fc_mcv != NULL)
	{
		bytea	   *fc_data = statext_mcv_serialize(fc_mcv, fc_stats);

		fc_nulls[Anum_pg_statistic_ext_data_stxdmcv - 1] = (fc_data == NULL);
		fc_values[Anum_pg_statistic_ext_data_stxdmcv - 1] = PointerGetDatum(fc_data);
	}
	if (fc_exprs != (Datum) 0)
	{
		fc_nulls[Anum_pg_statistic_ext_data_stxdexpr - 1] = false;
		fc_values[Anum_pg_statistic_ext_data_stxdexpr - 1] = fc_exprs;
	}

	/*
	 * Delete the old tuple if it exists, and insert a new one. It's easier
	 * than trying to update or insert, based on various conditions.
	 */
	RemoveStatisticsDataById(fc_statOid, fc_inh);

	/* form and insert a new tuple */
	fc_stup = heap_form_tuple(RelationGetDescr(pg_stextdata), fc_values, fc_nulls);
	CatalogTupleInsert(pg_stextdata, fc_stup);

	heap_freetuple(fc_stup);

	table_close(pg_stextdata, RowExclusiveLock);
}

/* initialize multi-dimensional sort */
MultiSortSupport
multi_sort_init(int fc_ndims)
{
	MultiSortSupport fc_mss;

	Assert(fc_ndims >= 2);

	fc_mss = (MultiSortSupport) palloc0(offsetof(MultiSortSupportData, ssup)
									 + sizeof(SortSupportData) * fc_ndims);

	fc_mss->ndims = fc_ndims;

	return fc_mss;
}

/*
 * Prepare sort support info using the given sort operator and collation
 * at the position 'sortdim'
 */
void multi_sort_add_dimension(MultiSortSupport fc_mss, int fc_sortdim,
						 Oid fc_oper, Oid fc_collation)
{
	SortSupport fc_ssup = &fc_mss->ssup[fc_sortdim];

	fc_ssup->ssup_cxt = CurrentMemoryContext;
	fc_ssup->ssup_collation = fc_collation;
	fc_ssup->ssup_nulls_first = false;

	PrepareSortSupportFromOrderingOp(fc_oper, fc_ssup);
}

/* compare all the dimensions in the selected order */
int multi_sort_compare(const void *fc_a, const void *fc_b, void *fc_arg)
{
	MultiSortSupport fc_mss = (MultiSortSupport) fc_arg;
	SortItem   *fc_ia = (SortItem *) fc_a;
	SortItem   *fc_ib = (SortItem *) fc_b;
	int			fc_i;

	for (fc_i = 0; fc_i < fc_mss->ndims; fc_i++)
	{
		int			fc_compare;

		fc_compare = ApplySortComparator(fc_ia->values[fc_i], fc_ia->isnull[fc_i],
									  fc_ib->values[fc_i], fc_ib->isnull[fc_i],
									  &fc_mss->ssup[fc_i]);

		if (fc_compare != 0)
			return fc_compare;
	}

	/* equal by default */
	return 0;
}

/* compare selected dimension */
int multi_sort_compare_dim(int fc_dim, const SortItem *fc_a, const SortItem *fc_b,
					   MultiSortSupport fc_mss)
{
	return ApplySortComparator(fc_a->values[fc_dim], fc_a->isnull[fc_dim],
							   fc_b->values[fc_dim], fc_b->isnull[fc_dim],
							   &fc_mss->ssup[fc_dim]);
}

int multi_sort_compare_dims(int fc_start, int fc_end,
						const SortItem *fc_a, const SortItem *fc_b,
						MultiSortSupport fc_mss)
{
	int			fc_dim;

	for (fc_dim = fc_start; fc_dim <= fc_end; fc_dim++)
	{
		int			fc_r = ApplySortComparator(fc_a->values[fc_dim], fc_a->isnull[fc_dim],
											fc_b->values[fc_dim], fc_b->isnull[fc_dim],
											&fc_mss->ssup[fc_dim]);

		if (fc_r != 0)
			return fc_r;
	}

	return 0;
}

int compare_scalars_simple(const void *fc_a, const void *fc_b, void *fc_arg)
{
	return compare_datums_simple(*(Datum *) fc_a,
								 *(Datum *) fc_b,
								 (SortSupport) fc_arg);
}

int compare_datums_simple(Datum fc_a, Datum fc_b, SortSupport fc_ssup)
{
	return ApplySortComparator(fc_a, false, fc_b, false, fc_ssup);
}

/*
 * build_attnums_array
 *		Transforms a bitmap into an array of AttrNumber values.
 *
 * This is used for extended statistics only, so all the attributes must be
 * user-defined. That means offsetting by FirstLowInvalidHeapAttributeNumber
 * is not necessary here (and when querying the bitmap).
 */
AttrNumber * build_attnums_array(Bitmapset *fc_attrs, int fc_nexprs, int *fc_numattrs)
{
	int			fc_i,
				fc_j;
	AttrNumber *fc_attnums;
	int			fc_num = bms_num_members(fc_attrs);

	if (fc_numattrs)
		*fc_numattrs = fc_num;

	/* build attnums from the bitmapset */
	fc_attnums = (AttrNumber *) palloc(sizeof(AttrNumber) * fc_num);
	fc_i = 0;
	fc_j = -1;
	while ((fc_j = bms_next_member(fc_attrs, fc_j)) >= 0)
	{
		int			fc_attnum = (fc_j - fc_nexprs);

		/*
		 * Make sure the bitmap contains only user-defined attributes. As
		 * bitmaps can't contain negative values, this can be violated in two
		 * ways. Firstly, the bitmap might contain 0 as a member, and secondly
		 * the integer value might be larger than MaxAttrNumber.
		 */
		Assert(AttributeNumberIsValid(fc_attnum));
		Assert(fc_attnum <= MaxAttrNumber);
		Assert(fc_attnum >= (-fc_nexprs));

		fc_attnums[fc_i++] = (AttrNumber) fc_attnum;

		/* protect against overflows */
		Assert(fc_i <= fc_num);
	}

	return fc_attnums;
}

/*
 * build_sorted_items
 *		build a sorted array of SortItem with values from rows
 *
 * Note: All the memory is allocated in a single chunk, so that the caller
 * can simply pfree the return value to release all of it.
 */
SortItem *
build_sorted_items(StatsBuildData *fc_data, int *fc_nitems,
				   MultiSortSupport fc_mss,
				   int fc_numattrs, AttrNumber *fc_attnums)
{
	int			fc_i,
				fc_j,
				fc_len,
				fc_nrows;
	int			fc_nvalues = fc_data->numrows * fc_numattrs;

	SortItem   *fc_items;
	Datum	   *fc_values;
	bool	   *fc_isnull;
	char	   *fc_ptr;
	int		   *fc_typlen;

	/* Compute the total amount of memory we need (both items and values). */
	fc_len = fc_data->numrows * sizeof(SortItem) + fc_nvalues * (sizeof(Datum) + sizeof(bool));

	/* Allocate the memory and split it into the pieces. */
	fc_ptr = palloc0(fc_len);

	/* items to sort */
	fc_items = (SortItem *) fc_ptr;
	fc_ptr += fc_data->numrows * sizeof(SortItem);

	/* values and null flags */
	fc_values = (Datum *) fc_ptr;
	fc_ptr += fc_nvalues * sizeof(Datum);

	fc_isnull = (bool *) fc_ptr;
	fc_ptr += fc_nvalues * sizeof(bool);

	/* make sure we consumed the whole buffer exactly */
	Assert((fc_ptr - (char *) fc_items) == fc_len);

	/* fix the pointers to Datum and bool arrays */
	fc_nrows = 0;
	for (fc_i = 0; fc_i < fc_data->numrows; fc_i++)
	{
		fc_items[fc_nrows].values = &fc_values[fc_nrows * fc_numattrs];
		fc_items[fc_nrows].isnull = &fc_isnull[fc_nrows * fc_numattrs];

		fc_nrows++;
	}

	/* build a local cache of typlen for all attributes */
	fc_typlen = (int *) palloc(sizeof(int) * fc_data->nattnums);
	for (fc_i = 0; fc_i < fc_data->nattnums; fc_i++)
		fc_typlen[fc_i] = get_typlen(fc_data->stats[fc_i]->attrtypid);

	fc_nrows = 0;
	for (fc_i = 0; fc_i < fc_data->numrows; fc_i++)
	{
		bool		fc_toowide = false;

		/* load the values/null flags from sample rows */
		for (fc_j = 0; fc_j < fc_numattrs; fc_j++)
		{
			Datum		fc_value;
			bool		fc_isnull;
			int			fc_attlen;
			AttrNumber	fc_attnum = fc_attnums[fc_j];

			int			fc_idx;

			/* match attnum to the pre-calculated data */
			for (fc_idx = 0; fc_idx < fc_data->nattnums; fc_idx++)
			{
				if (fc_attnum == fc_data->attnums[fc_idx])
					break;
			}

			Assert(fc_idx < fc_data->nattnums);

			fc_value = fc_data->values[fc_idx][fc_i];
			fc_isnull = fc_data->nulls[fc_idx][fc_i];
			fc_attlen = fc_typlen[fc_idx];

			/*
			 * If this is a varlena value, check if it's too wide and if yes
			 * then skip the whole item. Otherwise detoast the value.
			 *
			 * XXX It may happen that we've already detoasted some preceding
			 * values for the current item. We don't bother to cleanup those
			 * on the assumption that those are small (below WIDTH_THRESHOLD)
			 * and will be discarded at the end of analyze.
			 */
			if ((!fc_isnull) && (fc_attlen == -1))
			{
				if (toast_raw_datum_size(fc_value) > WIDTH_THRESHOLD)
				{
					fc_toowide = true;
					break;
				}

				fc_value = PointerGetDatum(PG_DETOAST_DATUM(fc_value));
			}

			fc_items[fc_nrows].values[fc_j] = fc_value;
			fc_items[fc_nrows].isnull[fc_j] = fc_isnull;
		}

		if (fc_toowide)
			continue;

		fc_nrows++;
	}

	/* store the actual number of items (ignoring the too-wide ones) */
	*fc_nitems = fc_nrows;

	/* all items were too wide */
	if (fc_nrows == 0)
	{
		/* everything is allocated as a single chunk */
		pfree(fc_items);
		return NULL;
	}

	/* do the sort, using the multi-sort */
	qsort_interruptible((void *) fc_items, fc_nrows, sizeof(SortItem),
						multi_sort_compare, fc_mss);

	return fc_items;
}

/*
 * has_stats_of_kind
 *		Check whether the list contains statistic of a given kind
 */
bool has_stats_of_kind(List *fc_stats, char fc_requiredkind)
{
	ListCell   *fc_l;

	foreach(fc_l, fc_stats)
	{
		StatisticExtInfo *fc_stat = (StatisticExtInfo *) lfirst(fc_l);

		if (fc_stat->kind == fc_requiredkind)
			return true;
	}

	return false;
}

/*
 * stat_find_expression
 *		Search for an expression in statistics object's list of expressions.
 *
 * Returns the index of the expression in the statistics object's list of
 * expressions, or -1 if not found.
 */
static int fc_stat_find_expression(StatisticExtInfo *fc_stat, Node *fc_expr)
{
	ListCell   *fc_lc;
	int			fc_idx;

	fc_idx = 0;
	foreach(fc_lc, fc_stat->exprs)
	{
		Node	   *fc_stat_expr = (Node *) lfirst(fc_lc);

		if (equal(fc_stat_expr, fc_expr))
			return fc_idx;
		fc_idx++;
	}

	/* Expression not found */
	return -1;
}

/*
 * stat_covers_expressions
 * 		Test whether a statistics object covers all expressions in a list.
 *
 * Returns true if all expressions are covered.  If expr_idxs is non-NULL, it
 * is populated with the indexes of the expressions found.
 */
static bool fc_stat_covers_expressions(StatisticExtInfo *fc_stat, List *fc_exprs,
						Bitmapset **fc_expr_idxs)
{
	ListCell   *fc_lc;

	foreach(fc_lc, fc_exprs)
	{
		Node	   *fc_expr = (Node *) lfirst(fc_lc);
		int			fc_expr_idx;

		fc_expr_idx = fc_stat_find_expression(fc_stat, fc_expr);
		if (fc_expr_idx == -1)
			return false;

		if (fc_expr_idxs != NULL)
			*fc_expr_idxs = bms_add_member(*fc_expr_idxs, fc_expr_idx);
	}

	/* If we reach here, all expressions are covered */
	return true;
}

/*
 * choose_best_statistics
 *		Look for and return statistics with the specified 'requiredkind' which
 *		have keys that match at least two of the given attnums.  Return NULL if
 *		there's no match.
 *
 * The current selection criteria is very simple - we choose the statistics
 * object referencing the most attributes in covered (and still unestimated
 * clauses), breaking ties in favor of objects with fewer keys overall.
 *
 * The clause_attnums is an array of bitmaps, storing attnums for individual
 * clauses. A NULL element means the clause is either incompatible or already
 * estimated.
 *
 * XXX If multiple statistics objects tie on both criteria, then which object
 * is chosen depends on the order that they appear in the stats list. Perhaps
 * further tiebreakers are needed.
 */
StatisticExtInfo *
choose_best_statistics(List *fc_stats, char fc_requiredkind, bool fc_inh,
					   Bitmapset **fc_clause_attnums, List **fc_clause_exprs,
					   int fc_nclauses)
{
	ListCell   *fc_lc;
	StatisticExtInfo *fc_best_match = NULL;
	int			fc_best_num_matched = 2;	/* goal #1: maximize */
	int			fc_best_match_keys = (STATS_MAX_DIMENSIONS + 1);	/* goal #2: minimize */

	foreach(fc_lc, fc_stats)
	{
		int			fc_i;
		StatisticExtInfo *fc_info = (StatisticExtInfo *) lfirst(fc_lc);
		Bitmapset  *fc_matched_attnums = NULL;
		Bitmapset  *fc_matched_exprs = NULL;
		int			fc_num_matched;
		int			fc_numkeys;

		/* skip statistics that are not of the correct type */
		if (fc_info->kind != fc_requiredkind)
			continue;

		/* skip statistics with mismatching inheritance flag */
		if (fc_info->inherit != fc_inh)
			continue;

		/*
		 * Collect attributes and expressions in remaining (unestimated)
		 * clauses fully covered by this statistic object.
		 *
		 * We know already estimated clauses have both clause_attnums and
		 * clause_exprs set to NULL. We leave the pointers NULL if already
		 * estimated, or we reset them to NULL after estimating the clause.
		 */
		for (fc_i = 0; fc_i < fc_nclauses; fc_i++)
		{
			Bitmapset  *fc_expr_idxs = NULL;

			/* ignore incompatible/estimated clauses */
			if (!fc_clause_attnums[fc_i] && !fc_clause_exprs[fc_i])
				continue;

			/* ignore clauses that are not covered by this object */
			if (!bms_is_subset(fc_clause_attnums[fc_i], fc_info->keys) ||
				!fc_stat_covers_expressions(fc_info, fc_clause_exprs[fc_i], &fc_expr_idxs))
				continue;

			/* record attnums and indexes of expressions covered */
			fc_matched_attnums = bms_add_members(fc_matched_attnums, fc_clause_attnums[fc_i]);
			fc_matched_exprs = bms_add_members(fc_matched_exprs, fc_expr_idxs);
		}

		fc_num_matched = bms_num_members(fc_matched_attnums) + bms_num_members(fc_matched_exprs);

		bms_free(fc_matched_attnums);
		bms_free(fc_matched_exprs);

		/*
		 * save the actual number of keys in the stats so that we can choose
		 * the narrowest stats with the most matching keys.
		 */
		fc_numkeys = bms_num_members(fc_info->keys) + list_length(fc_info->exprs);

		/*
		 * Use this object when it increases the number of matched attributes
		 * and expressions or when it matches the same number of attributes
		 * and expressions but these stats have fewer keys than any previous
		 * match.
		 */
		if (fc_num_matched > fc_best_num_matched ||
			(fc_num_matched == fc_best_num_matched && fc_numkeys < fc_best_match_keys))
		{
			fc_best_match = fc_info;
			fc_best_num_matched = fc_num_matched;
			fc_best_match_keys = fc_numkeys;
		}
	}

	return fc_best_match;
}

/*
 * statext_is_compatible_clause_internal
 *		Determines if the clause is compatible with MCV lists.
 *
 * To be compatible, the given clause must be a combination of supported
 * clauses built from Vars or sub-expressions (where a sub-expression is
 * something that exactly matches an expression found in statistics objects).
 * This function recursively examines the clause and extracts any
 * sub-expressions that will need to be matched against statistics.
 *
 * Currently, we only support the following types of clauses:
 *
 * (a) OpExprs of the form (Var/Expr op Const), or (Const op Var/Expr), where
 * the op is one of ("=", "<", ">", ">=", "<=")
 *
 * (b) (Var/Expr IS [NOT] NULL)
 *
 * (c) combinations using AND/OR/NOT
 *
 * (d) ScalarArrayOpExprs of the form (Var/Expr op ANY (Const)) or
 * (Var/Expr op ALL (Const))
 *
 * In the future, the range of supported clauses may be expanded to more
 * complex cases, for example (Var op Var).
 *
 * Arguments:
 * clause: (sub)clause to be inspected (bare clause, not a RestrictInfo)
 * relid: rel that all Vars in clause must belong to
 * *attnums: input/output parameter collecting attribute numbers of all
 *		mentioned Vars.  Note that we do not offset the attribute numbers,
 *		so we can't cope with system columns.
 * *exprs: input/output parameter collecting primitive subclauses within
 *		the clause tree
 *
 * Returns false if there is something we definitively can't handle.
 * On true return, we can proceed to match the *exprs against statistics.
 */
static bool fc_statext_is_compatible_clause_internal(PlannerInfo *fc_root, Node *fc_clause,
									  Index fc_relid, Bitmapset **fc_attnums,
									  List **fc_exprs)
{
	/* Look inside any binary-compatible relabeling (as in examine_variable) */
	if (IsA(fc_clause, RelabelType))
		fc_clause = (Node *) ((RelabelType *) fc_clause)->arg;

	/* plain Var references (boolean Vars or recursive checks) */
	if (IsA(fc_clause, Var))
	{
		Var		   *fc_var = (Var *) fc_clause;

		/* Ensure var is from the correct relation */
		if (fc_var->varno != fc_relid)
			return false;

		/* we also better ensure the Var is from the current level */
		if (fc_var->varlevelsup > 0)
			return false;

		/*
		 * Also reject system attributes and whole-row Vars (we don't allow
		 * stats on those).
		 */
		if (!AttrNumberIsForUserDefinedAttr(fc_var->varattno))
			return false;

		/* OK, record the attnum for later permissions checks. */
		*fc_attnums = bms_add_member(*fc_attnums, fc_var->varattno);

		return true;
	}

	/* (Var/Expr op Const) or (Const op Var/Expr) */
	if (is_opclause(fc_clause))
	{
		RangeTblEntry *fc_rte = fc_root->simple_rte_array[fc_relid];
		OpExpr	   *fc_expr = (OpExpr *) fc_clause;
		Node	   *fc_clause_expr;

		/* Only expressions with two arguments are considered compatible. */
		if (list_length(fc_expr->args) != 2)
			return false;

		/* Check if the expression has the right shape */
		if (!examine_opclause_args(fc_expr->args, &fc_clause_expr, NULL, NULL))
			return false;

		/*
		 * If it's not one of the supported operators ("=", "<", ">", etc.),
		 * just ignore the clause, as it's not compatible with MCV lists.
		 *
		 * This uses the function for estimating selectivity, not the operator
		 * directly (a bit awkward, but well ...).
		 */
		switch (get_oprrest(fc_expr->opno))
		{
			case F_EQSEL:
			case F_NEQSEL:
			case F_SCALARLTSEL:
			case F_SCALARLESEL:
			case F_SCALARGTSEL:
			case F_SCALARGESEL:
				/* supported, will continue with inspection of the Var/Expr */
				break;

			default:
				/* other estimators are considered unknown/unsupported */
				return false;
		}

		/*
		 * If there are any securityQuals on the RTE from security barrier
		 * views or RLS policies, then the user may not have access to all the
		 * table's data, and we must check that the operator is leak-proof.
		 *
		 * If the operator is leaky, then we must ignore this clause for the
		 * purposes of estimating with MCV lists, otherwise the operator might
		 * reveal values from the MCV list that the user doesn't have
		 * permission to see.
		 */
		if (fc_rte->securityQuals != NIL &&
			!get_func_leakproof(get_opcode(fc_expr->opno)))
			return false;

		/* Check (Var op Const) or (Const op Var) clauses by recursing. */
		if (IsA(fc_clause_expr, Var))
			return fc_statext_is_compatible_clause_internal(fc_root, fc_clause_expr,
														 fc_relid, fc_attnums, fc_exprs);

		/* Otherwise we have (Expr op Const) or (Const op Expr). */
		*fc_exprs = lappend(*fc_exprs, fc_clause_expr);
		return true;
	}

	/* Var/Expr IN Array */
	if (IsA(fc_clause, ScalarArrayOpExpr))
	{
		RangeTblEntry *fc_rte = fc_root->simple_rte_array[fc_relid];
		ScalarArrayOpExpr *fc_expr = (ScalarArrayOpExpr *) fc_clause;
		Node	   *fc_clause_expr;
		bool		fc_expronleft;

		/* Only expressions with two arguments are considered compatible. */
		if (list_length(fc_expr->args) != 2)
			return false;

		/* Check if the expression has the right shape (one Var, one Const) */
		if (!examine_opclause_args(fc_expr->args, &fc_clause_expr, NULL, &fc_expronleft))
			return false;

		/* We only support Var on left, Const on right */
		if (!fc_expronleft)
			return false;

		/*
		 * If it's not one of the supported operators ("=", "<", ">", etc.),
		 * just ignore the clause, as it's not compatible with MCV lists.
		 *
		 * This uses the function for estimating selectivity, not the operator
		 * directly (a bit awkward, but well ...).
		 */
		switch (get_oprrest(fc_expr->opno))
		{
			case F_EQSEL:
			case F_NEQSEL:
			case F_SCALARLTSEL:
			case F_SCALARLESEL:
			case F_SCALARGTSEL:
			case F_SCALARGESEL:
				/* supported, will continue with inspection of the Var/Expr */
				break;

			default:
				/* other estimators are considered unknown/unsupported */
				return false;
		}

		/*
		 * If there are any securityQuals on the RTE from security barrier
		 * views or RLS policies, then the user may not have access to all the
		 * table's data, and we must check that the operator is leak-proof.
		 *
		 * If the operator is leaky, then we must ignore this clause for the
		 * purposes of estimating with MCV lists, otherwise the operator might
		 * reveal values from the MCV list that the user doesn't have
		 * permission to see.
		 */
		if (fc_rte->securityQuals != NIL &&
			!get_func_leakproof(get_opcode(fc_expr->opno)))
			return false;

		/* Check Var IN Array clauses by recursing. */
		if (IsA(fc_clause_expr, Var))
			return fc_statext_is_compatible_clause_internal(fc_root, fc_clause_expr,
														 fc_relid, fc_attnums, fc_exprs);

		/* Otherwise we have Expr IN Array. */
		*fc_exprs = lappend(*fc_exprs, fc_clause_expr);
		return true;
	}

	/* AND/OR/NOT clause */
	if (is_andclause(fc_clause) ||
		is_orclause(fc_clause) ||
		is_notclause(fc_clause))
	{
		/*
		 * AND/OR/NOT-clauses are supported if all sub-clauses are supported
		 *
		 * Perhaps we could improve this by handling mixed cases, when some of
		 * the clauses are supported and some are not. Selectivity for the
		 * supported subclauses would be computed using extended statistics,
		 * and the remaining clauses would be estimated using the traditional
		 * algorithm (product of selectivities).
		 *
		 * It however seems overly complex, and in a way we already do that
		 * because if we reject the whole clause as unsupported here, it will
		 * be eventually passed to clauselist_selectivity() which does exactly
		 * this (split into supported/unsupported clauses etc).
		 */
		BoolExpr   *fc_expr = (BoolExpr *) fc_clause;
		ListCell   *fc_lc;

		foreach(fc_lc, fc_expr->args)
		{
			/*
			 * If we find an incompatible clause in the arguments, treat the
			 * whole clause as incompatible.
			 */
			if (!fc_statext_is_compatible_clause_internal(fc_root,
													   (Node *) lfirst(fc_lc),
													   fc_relid, fc_attnums, fc_exprs))
				return false;
		}

		return true;
	}

	/* Var/Expr IS NULL */
	if (IsA(fc_clause, NullTest))
	{
		NullTest   *fc_nt = (NullTest *) fc_clause;

		/* Check Var IS NULL clauses by recursing. */
		if (IsA(fc_nt->arg, Var))
			return fc_statext_is_compatible_clause_internal(fc_root, (Node *) (fc_nt->arg),
														 fc_relid, fc_attnums, fc_exprs);

		/* Otherwise we have Expr IS NULL. */
		*fc_exprs = lappend(*fc_exprs, fc_nt->arg);
		return true;
	}

	/*
	 * Treat any other expressions as bare expressions to be matched against
	 * expressions in statistics objects.
	 */
	*fc_exprs = lappend(*fc_exprs, fc_clause);
	return true;
}

/*
 * statext_is_compatible_clause
 *		Determines if the clause is compatible with MCV lists.
 *
 * See statext_is_compatible_clause_internal, above, for the basic rules.
 * This layer deals with RestrictInfo superstructure and applies permissions
 * checks to verify that it's okay to examine all mentioned Vars.
 *
 * Arguments:
 * clause: clause to be inspected (in RestrictInfo form)
 * relid: rel that all Vars in clause must belong to
 * *attnums: input/output parameter collecting attribute numbers of all
 *		mentioned Vars.  Note that we do not offset the attribute numbers,
 *		so we can't cope with system columns.
 * *exprs: input/output parameter collecting primitive subclauses within
 *		the clause tree
 *
 * Returns false if there is something we definitively can't handle.
 * On true return, we can proceed to match the *exprs against statistics.
 */
static bool fc_statext_is_compatible_clause(PlannerInfo *fc_root, Node *fc_clause, Index fc_relid,
							 Bitmapset **fc_attnums, List **fc_exprs)
{
	RangeTblEntry *fc_rte = fc_root->simple_rte_array[fc_relid];
	RestrictInfo *fc_rinfo;
	int			fc_clause_relid;
	Oid			fc_userid;

	/*
	 * Special-case handling for bare BoolExpr AND clauses, because the
	 * restrictinfo machinery doesn't build RestrictInfos on top of AND
	 * clauses.
	 */
	if (is_andclause(fc_clause))
	{
		BoolExpr   *fc_expr = (BoolExpr *) fc_clause;
		ListCell   *fc_lc;

		/*
		 * Check that each sub-clause is compatible.  We expect these to be
		 * RestrictInfos.
		 */
		foreach(fc_lc, fc_expr->args)
		{
			if (!fc_statext_is_compatible_clause(fc_root, (Node *) lfirst(fc_lc),
											  fc_relid, fc_attnums, fc_exprs))
				return false;
		}

		return true;
	}

	/* Otherwise it must be a RestrictInfo. */
	if (!IsA(fc_clause, RestrictInfo))
		return false;
	fc_rinfo = (RestrictInfo *) fc_clause;

	/* Pseudoconstants are not really interesting here. */
	if (fc_rinfo->pseudoconstant)
		return false;

	/* Clauses referencing other varnos are incompatible. */
	if (!bms_get_singleton_member(fc_rinfo->clause_relids, &fc_clause_relid) ||
		fc_clause_relid != fc_relid)
		return false;

	/* Check the clause and determine what attributes it references. */
	if (!fc_statext_is_compatible_clause_internal(fc_root, (Node *) fc_rinfo->clause,
											   fc_relid, fc_attnums, fc_exprs))
		return false;

	/*
	 * Check that the user has permission to read all required attributes. Use
	 * checkAsUser if it's set, in case we're accessing the table via a view.
	 */
	fc_userid = fc_rte->checkAsUser ? fc_rte->checkAsUser : GetUserId();

	/* Table-level SELECT privilege is sufficient for all columns */
	if (pg_class_aclcheck(fc_rte->relid, fc_userid, ACL_SELECT) != ACLCHECK_OK)
	{
		Bitmapset  *fc_clause_attnums = NULL;
		int			fc_attnum = -1;

		/*
		 * We have to check per-column privileges.  *attnums has the attnums
		 * for individual Vars we saw, but there may also be Vars within
		 * subexpressions in *exprs.  We can use pull_varattnos() to extract
		 * those, but there's an impedance mismatch: attnums returned by
		 * pull_varattnos() are offset by FirstLowInvalidHeapAttributeNumber,
		 * while attnums within *attnums aren't.  Convert *attnums to the
		 * offset style so we can combine the results.
		 */
		while ((fc_attnum = bms_next_member(*fc_attnums, fc_attnum)) >= 0)
		{
			fc_clause_attnums =
				bms_add_member(fc_clause_attnums,
							   fc_attnum - FirstLowInvalidHeapAttributeNumber);
		}

		/* Now merge attnums from *exprs into clause_attnums */
		if (*fc_exprs != NIL)
			pull_varattnos((Node *) *fc_exprs, fc_relid, &fc_clause_attnums);

		fc_attnum = -1;
		while ((fc_attnum = bms_next_member(fc_clause_attnums, fc_attnum)) >= 0)
		{
			/* Undo the offset */
			AttrNumber	fc_attno = fc_attnum + FirstLowInvalidHeapAttributeNumber;

			if (fc_attno == InvalidAttrNumber)
			{
				/* Whole-row reference, so must have access to all columns */
				if (pg_attribute_aclcheck_all(fc_rte->relid, fc_userid, ACL_SELECT,
											  ACLMASK_ALL) != ACLCHECK_OK)
					return false;
			}
			else
			{
				if (pg_attribute_aclcheck(fc_rte->relid, fc_attno, fc_userid,
										  ACL_SELECT) != ACLCHECK_OK)
					return false;
			}
		}
	}

	/* If we reach here, the clause is OK */
	return true;
}

/*
 * statext_mcv_clauselist_selectivity
 *		Estimate clauses using the best multi-column statistics.
 *
 * Applies available extended (multi-column) statistics on a table. There may
 * be multiple applicable statistics (with respect to the clauses), in which
 * case we use greedy approach. In each round we select the best statistic on
 * a table (measured by the number of attributes extracted from the clauses
 * and covered by it), and compute the selectivity for the supplied clauses.
 * We repeat this process with the remaining clauses (if any), until none of
 * the available statistics can be used.
 *
 * One of the main challenges with using MCV lists is how to extrapolate the
 * estimate to the data not covered by the MCV list. To do that, we compute
 * not only the "MCV selectivity" (selectivities for MCV items matching the
 * supplied clauses), but also the following related selectivities:
 *
 * - simple selectivity:  Computed without extended statistics, i.e. as if the
 * columns/clauses were independent.
 *
 * - base selectivity:  Similar to simple selectivity, but is computed using
 * the extended statistic by adding up the base frequencies (that we compute
 * and store for each MCV item) of matching MCV items.
 *
 * - total selectivity: Selectivity covered by the whole MCV list.
 *
 * These are passed to mcv_combine_selectivities() which combines them to
 * produce a selectivity estimate that makes use of both per-column statistics
 * and the multi-column MCV statistics.
 *
 * 'estimatedclauses' is an input/output parameter.  We set bits for the
 * 0-based 'clauses' indexes we estimate for and also skip clause items that
 * already have a bit set.
 */
static Selectivity fc_statext_mcv_clauselist_selectivity(PlannerInfo *fc_root, List *fc_clauses, int fc_varRelid,
								   JoinType fc_jointype, SpecialJoinInfo *fc_sjinfo,
								   RelOptInfo *fc_rel, Bitmapset **fc_estimatedclauses,
								   bool fc_is_or)
{
	ListCell   *fc_l;
	Bitmapset **fc_list_attnums;	/* attnums extracted from the clause */
	List	  **fc_list_exprs;		/* expressions matched to any statistic */
	int			fc_listidx;
	Selectivity fc_sel = (fc_is_or) ? 0.0 : 1.0;
	RangeTblEntry *fc_rte = planner_rt_fetch(fc_rel->relid, fc_root);

	/* check if there's any stats that might be useful for us. */
	if (!has_stats_of_kind(fc_rel->statlist, STATS_EXT_MCV))
		return fc_sel;

	fc_list_attnums = (Bitmapset **) palloc(sizeof(Bitmapset *) *
										 list_length(fc_clauses));

	/* expressions extracted from complex expressions */
	fc_list_exprs = (List **) palloc(sizeof(Node *) * list_length(fc_clauses));

	/*
	 * Pre-process the clauses list to extract the attnums and expressions
	 * seen in each item.  We need to determine if there are any clauses which
	 * will be useful for selectivity estimations with extended stats.  Along
	 * the way we'll record all of the attnums and expressions for each clause
	 * in lists which we'll reference later so we don't need to repeat the
	 * same work again.
	 *
	 * We also skip clauses that we already estimated using different types of
	 * statistics (we treat them as incompatible).
	 */
	fc_listidx = 0;
	foreach(fc_l, fc_clauses)
	{
		Node	   *fc_clause = (Node *) lfirst(fc_l);
		Bitmapset  *fc_attnums = NULL;
		List	   *fc_exprs = NIL;

		if (!bms_is_member(fc_listidx, *fc_estimatedclauses) &&
			fc_statext_is_compatible_clause(fc_root, fc_clause, fc_rel->relid, &fc_attnums, &fc_exprs))
		{
			fc_list_attnums[fc_listidx] = fc_attnums;
			fc_list_exprs[fc_listidx] = fc_exprs;
		}
		else
		{
			fc_list_attnums[fc_listidx] = NULL;
			fc_list_exprs[fc_listidx] = NIL;
		}

		fc_listidx++;
	}

	/* apply as many extended statistics as possible */
	while (true)
	{
		StatisticExtInfo *fc_stat;
		List	   *fc_stat_clauses;
		Bitmapset  *fc_simple_clauses;

		/* find the best suited statistics object for these attnums */
		fc_stat = choose_best_statistics(fc_rel->statlist, STATS_EXT_MCV, fc_rte->inh,
									  fc_list_attnums, fc_list_exprs,
									  list_length(fc_clauses));

		/*
		 * if no (additional) matching stats could be found then we've nothing
		 * to do
		 */
		if (!fc_stat)
			break;

		/* Ensure choose_best_statistics produced an expected stats type. */
		Assert(fc_stat->kind == STATS_EXT_MCV);

		/* now filter the clauses to be estimated using the selected MCV */
		fc_stat_clauses = NIL;

		/* record which clauses are simple (single column or expression) */
		fc_simple_clauses = NULL;

		fc_listidx = -1;
		foreach(fc_l, fc_clauses)
		{
			/* Increment the index before we decide if to skip the clause. */
			fc_listidx++;

			/*
			 * Ignore clauses from which we did not extract any attnums or
			 * expressions (this needs to be consistent with what we do in
			 * choose_best_statistics).
			 *
			 * This also eliminates already estimated clauses - both those
			 * estimated before and during applying extended statistics.
			 *
			 * XXX This check is needed because both bms_is_subset and
			 * stat_covers_expressions return true for empty attnums and
			 * expressions.
			 */
			if (!fc_list_attnums[fc_listidx] && !fc_list_exprs[fc_listidx])
				continue;

			/*
			 * The clause was not estimated yet, and we've extracted either
			 * attnums or expressions from it. Ignore it if it's not fully
			 * covered by the chosen statistics object.
			 *
			 * We need to check both attributes and expressions, and reject if
			 * either is not covered.
			 */
			if (!bms_is_subset(fc_list_attnums[fc_listidx], fc_stat->keys) ||
				!fc_stat_covers_expressions(fc_stat, fc_list_exprs[fc_listidx], NULL))
				continue;

			/*
			 * Now we know the clause is compatible (we have either attnums or
			 * expressions extracted from it), and was not estimated yet.
			 */

			/* record simple clauses (single column or expression) */
			if ((fc_list_attnums[fc_listidx] == NULL &&
				 list_length(fc_list_exprs[fc_listidx]) == 1) ||
				(fc_list_exprs[fc_listidx] == NIL &&
				 bms_membership(fc_list_attnums[fc_listidx]) == BMS_SINGLETON))
				fc_simple_clauses = bms_add_member(fc_simple_clauses,
												list_length(fc_stat_clauses));

			/* add clause to list and mark it as estimated */
			fc_stat_clauses = lappend(fc_stat_clauses, (Node *) lfirst(fc_l));
			*fc_estimatedclauses = bms_add_member(*fc_estimatedclauses, fc_listidx);

			/*
			 * Reset the pointers, so that choose_best_statistics knows this
			 * clause was estimated and does not consider it again.
			 */
			bms_free(fc_list_attnums[fc_listidx]);
			fc_list_attnums[fc_listidx] = NULL;

			list_free(fc_list_exprs[fc_listidx]);
			fc_list_exprs[fc_listidx] = NULL;
		}

		if (fc_is_or)
		{
			bool	   *fc_or_matches = NULL;
			Selectivity fc_simple_or_sel = 0.0,
						fc_stat_sel = 0.0;
			MCVList    *fc_mcv_list;

			/* Load the MCV list stored in the statistics object */
			fc_mcv_list = statext_mcv_load(fc_stat->statOid, fc_rte->inh);

			/*
			 * Compute the selectivity of the ORed list of clauses covered by
			 * this statistics object by estimating each in turn and combining
			 * them using the formula P(A OR B) = P(A) + P(B) - P(A AND B).
			 * This allows us to use the multivariate MCV stats to better
			 * estimate the individual terms and their overlap.
			 *
			 * Each time we iterate this formula, the clause "A" above is
			 * equal to all the clauses processed so far, combined with "OR".
			 */
			fc_listidx = 0;
			foreach(fc_l, fc_stat_clauses)
			{
				Node	   *fc_clause = (Node *) lfirst(fc_l);
				Selectivity fc_simple_sel,
							fc_overlap_simple_sel,
							fc_mcv_sel,
							fc_mcv_basesel,
							fc_overlap_mcvsel,
							fc_overlap_basesel,
							fc_mcv_totalsel,
							fc_clause_sel,
							fc_overlap_sel;

				/*
				 * "Simple" selectivity of the next clause and its overlap
				 * with any of the previous clauses.  These are our initial
				 * estimates of P(B) and P(A AND B), assuming independence of
				 * columns/clauses.
				 */
				fc_simple_sel = clause_selectivity_ext(fc_root, fc_clause, fc_varRelid,
													fc_jointype, fc_sjinfo, false);

				fc_overlap_simple_sel = fc_simple_or_sel * fc_simple_sel;

				/*
				 * New "simple" selectivity of all clauses seen so far,
				 * assuming independence.
				 */
				fc_simple_or_sel += fc_simple_sel - fc_overlap_simple_sel;
				CLAMP_PROBABILITY(fc_simple_or_sel);

				/*
				 * Multi-column estimate of this clause using MCV statistics,
				 * along with base and total selectivities, and corresponding
				 * selectivities for the overlap term P(A AND B).
				 */
				fc_mcv_sel = mcv_clause_selectivity_or(fc_root, fc_stat, fc_mcv_list,
													fc_clause, &fc_or_matches,
													&fc_mcv_basesel,
													&fc_overlap_mcvsel,
													&fc_overlap_basesel,
													&fc_mcv_totalsel);

				/*
				 * Combine the simple and multi-column estimates.
				 *
				 * If this clause is a simple single-column clause, then we
				 * just use the simple selectivity estimate for it, since the
				 * multi-column statistics are unlikely to improve on that
				 * (and in fact could make it worse).  For the overlap, we
				 * always make use of the multi-column statistics.
				 */
				if (bms_is_member(fc_listidx, fc_simple_clauses))
					fc_clause_sel = fc_simple_sel;
				else
					fc_clause_sel = mcv_combine_selectivities(fc_simple_sel,
														   fc_mcv_sel,
														   fc_mcv_basesel,
														   fc_mcv_totalsel);

				fc_overlap_sel = mcv_combine_selectivities(fc_overlap_simple_sel,
														fc_overlap_mcvsel,
														fc_overlap_basesel,
														fc_mcv_totalsel);

				/* Factor these into the result for this statistics object */
				fc_stat_sel += fc_clause_sel - fc_overlap_sel;
				CLAMP_PROBABILITY(fc_stat_sel);

				fc_listidx++;
			}

			/*
			 * Factor the result for this statistics object into the overall
			 * result.  We treat the results from each separate statistics
			 * object as independent of one another.
			 */
			fc_sel = fc_sel + fc_stat_sel - fc_sel * fc_stat_sel;
		}
		else					/* Implicitly-ANDed list of clauses */
		{
			Selectivity fc_simple_sel,
						fc_mcv_sel,
						fc_mcv_basesel,
						fc_mcv_totalsel,
						fc_stat_sel;

			/*
			 * "Simple" selectivity, i.e. without any extended statistics,
			 * essentially assuming independence of the columns/clauses.
			 */
			fc_simple_sel = clauselist_selectivity_ext(fc_root, fc_stat_clauses,
													fc_varRelid, fc_jointype,
													fc_sjinfo, false);

			/*
			 * Multi-column estimate using MCV statistics, along with base and
			 * total selectivities.
			 */
			fc_mcv_sel = mcv_clauselist_selectivity(fc_root, fc_stat, fc_stat_clauses,
												 fc_varRelid, fc_jointype, fc_sjinfo,
												 fc_rel, &fc_mcv_basesel,
												 &fc_mcv_totalsel);

			/* Combine the simple and multi-column estimates. */
			fc_stat_sel = mcv_combine_selectivities(fc_simple_sel,
												 fc_mcv_sel,
												 fc_mcv_basesel,
												 fc_mcv_totalsel);

			/* Factor this into the overall result */
			fc_sel *= fc_stat_sel;
		}
	}

	return fc_sel;
}

/*
 * statext_clauselist_selectivity
 *		Estimate clauses using the best multi-column statistics.
 */
Selectivity statext_clauselist_selectivity(PlannerInfo *fc_root, List *fc_clauses, int fc_varRelid,
							   JoinType fc_jointype, SpecialJoinInfo *fc_sjinfo,
							   RelOptInfo *fc_rel, Bitmapset **fc_estimatedclauses,
							   bool fc_is_or)
{
	Selectivity fc_sel;

	/* First, try estimating clauses using a multivariate MCV list. */
	fc_sel = fc_statext_mcv_clauselist_selectivity(fc_root, fc_clauses, fc_varRelid, fc_jointype,
											 fc_sjinfo, fc_rel, fc_estimatedclauses, fc_is_or);

	/*
	 * Functional dependencies only work for clauses connected by AND, so for
	 * OR clauses we're done.
	 */
	if (fc_is_or)
		return fc_sel;

	/*
	 * Then, apply functional dependencies on the remaining clauses by calling
	 * dependencies_clauselist_selectivity.  Pass 'estimatedclauses' so the
	 * function can properly skip clauses already estimated above.
	 *
	 * The reasoning for applying dependencies last is that the more complex
	 * stats can track more complex correlations between the attributes, and
	 * so may be considered more reliable.
	 *
	 * For example, MCV list can give us an exact selectivity for values in
	 * two columns, while functional dependencies can only provide information
	 * about the overall strength of the dependency.
	 */
	fc_sel *= dependencies_clauselist_selectivity(fc_root, fc_clauses, fc_varRelid,
											   fc_jointype, fc_sjinfo, fc_rel,
											   fc_estimatedclauses);

	return fc_sel;
}

/*
 * examine_opclause_args
 *		Split an operator expression's arguments into Expr and Const parts.
 *
 * Attempts to match the arguments to either (Expr op Const) or (Const op
 * Expr), possibly with a RelabelType on top. When the expression matches this
 * form, returns true, otherwise returns false.
 *
 * Optionally returns pointers to the extracted Expr/Const nodes, when passed
 * non-null pointers (exprp, cstp and expronleftp). The expronleftp flag
 * specifies on which side of the operator we found the expression node.
 */
bool examine_opclause_args(List *fc_args, Node **fc_exprp, Const **fc_cstp,
					  bool *fc_expronleftp)
{
	Node	   *fc_expr;
	Const	   *fc_cst;
	bool		fc_expronleft;
	Node	   *fc_leftop,
			   *fc_rightop;

	/* enforced by statext_is_compatible_clause_internal */
	Assert(list_length(fc_args) == 2);

	fc_leftop = linitial(fc_args);
	fc_rightop = lsecond(fc_args);

	/* strip RelabelType from either side of the expression */
	if (IsA(fc_leftop, RelabelType))
		fc_leftop = (Node *) ((RelabelType *) fc_leftop)->arg;

	if (IsA(fc_rightop, RelabelType))
		fc_rightop = (Node *) ((RelabelType *) fc_rightop)->arg;

	if (IsA(fc_rightop, Const))
	{
		fc_expr = (Node *) fc_leftop;
		fc_cst = (Const *) fc_rightop;
		fc_expronleft = true;
	}
	else if (IsA(fc_leftop, Const))
	{
		fc_expr = (Node *) fc_rightop;
		fc_cst = (Const *) fc_leftop;
		fc_expronleft = false;
	}
	else
		return false;

	/* return pointers to the extracted parts if requested */
	if (fc_exprp)
		*fc_exprp = fc_expr;

	if (fc_cstp)
		*fc_cstp = fc_cst;

	if (fc_expronleftp)
		*fc_expronleftp = fc_expronleft;

	return true;
}


/*
 * Compute statistics about expressions of a relation.
 */
static void fc_compute_expr_stats(Relation fc_onerel, double fc_totalrows,
				   AnlExprData *fc_exprdata, int fc_nexprs,
				   HeapTuple *fc_rows, int fc_numrows)
{
	MemoryContext fc_expr_context,
				fc_old_context;
	int			fc_ind,
				fc_i;

	fc_expr_context = AllocSetContextCreate(CurrentMemoryContext,
										 "Analyze Expression",
										 ALLOCSET_DEFAULT_SIZES);
	fc_old_context = MemoryContextSwitchTo(fc_expr_context);

	for (fc_ind = 0; fc_ind < fc_nexprs; fc_ind++)
	{
		AnlExprData *fc_thisdata = &fc_exprdata[fc_ind];
		VacAttrStats *fc_stats = fc_thisdata->vacattrstat;
		Node	   *fc_expr = fc_thisdata->expr;
		TupleTableSlot *fc_slot;
		EState	   *fc_estate;
		ExprContext *fc_econtext;
		Datum	   *fc_exprvals;
		bool	   *fc_exprnulls;
		ExprState  *fc_exprstate;
		int			fc_tcnt;

		/* Are we still in the main context? */
		Assert(CurrentMemoryContext == fc_expr_context);

		/*
		 * Need an EState for evaluation of expressions.  Create it in the
		 * per-expression context to be sure it gets cleaned up at the bottom
		 * of the loop.
		 */
		fc_estate = CreateExecutorState();
		fc_econtext = GetPerTupleExprContext(fc_estate);

		/* Set up expression evaluation state */
		fc_exprstate = ExecPrepareExpr((Expr *) fc_expr, fc_estate);

		/* 还需要一个槽来保存当前的堆元组 */  
		fc_slot = MakeSingleTupleTableSlot(RelationGetDescr(fc_onerel),
										&TTSOpsHeapTuple);

		/* 安排econtext的扫描元组为待测试的元组 */
		fc_econtext->ecxt_scantuple = fc_slot;

		/* Compute and save expression values */
		fc_exprvals = (Datum *) palloc(fc_numrows * sizeof(Datum));
		fc_exprnulls = (bool *) palloc(fc_numrows * sizeof(bool));

		fc_tcnt = 0;
		for (fc_i = 0; fc_i < fc_numrows; fc_i++)
		{
			Datum		fc_datum;
			bool		fc_isnull;

			/*
			 * Reset the per-tuple context each time, to reclaim any cruft
			 * left behind by evaluating the statistics expressions.
			 */
			ResetExprContext(fc_econtext);

			/* Set up for expression evaluation */
			ExecStoreHeapTuple(fc_rows[fc_i], fc_slot, false);

			/*
			 * Evaluate the expression. We do this in the per-tuple context so
			 * as not to leak memory, and then copy the result into the
			 * context created at the beginning of this function.
			 */
			fc_datum = ExecEvalExprSwitchContext(fc_exprstate,
											  GetPerTupleExprContext(fc_estate),
											  &fc_isnull);
			if (fc_isnull)
			{
				fc_exprvals[fc_tcnt] = (Datum) 0;
				fc_exprnulls[fc_tcnt] = true;
			}
			else
			{
				/* Make sure we copy the data into the context. */
				Assert(CurrentMemoryContext == fc_expr_context);

				fc_exprvals[fc_tcnt] = datumCopy(fc_datum,
										   fc_stats->attrtype->typbyval,
										   fc_stats->attrtype->typlen);
				fc_exprnulls[fc_tcnt] = false;
			}

			fc_tcnt++;
		}

		/*
		 * Now we can compute the statistics for the expression columns.
		 *
		 * XXX Unlike compute_index_stats we don't need to switch and reset
		 * memory contexts here, because we're only computing stats for a
		 * single expression (and not iterating over many indexes), so we just
		 * do it in expr_context. Note that compute_stats copies the result
		 * into stats->anl_context, so it does not disappear.
		 */
		if (fc_tcnt > 0)
		{
			AttributeOpts *fc_aopt =
			get_attribute_options(fc_stats->attr->attrelid,
								  fc_stats->attr->attnum);

			fc_stats->exprvals = fc_exprvals;
			fc_stats->exprnulls = fc_exprnulls;
			fc_stats->rowstride = 1;
			fc_stats->compute_stats(fc_stats,
								 fc_expr_fetch_func,
								 fc_tcnt,
								 fc_tcnt);

			/*
			 * If the n_distinct option is specified, it overrides the above
			 * computation.
			 */
			if (fc_aopt != NULL && fc_aopt->n_distinct != 0.0)
				fc_stats->stadistinct = fc_aopt->n_distinct;
		}

		/* 并进行清理 */
		MemoryContextSwitchTo(fc_expr_context);

		ExecDropSingleTupleTableSlot(fc_slot);
		FreeExecutorState(fc_estate);
		MemoryContextResetAndDeleteChildren(fc_expr_context);
	}

	MemoryContextSwitchTo(fc_old_context);
	MemoryContextDelete(fc_expr_context);
}


/*
 * Fetch function for analyzing statistics object expressions.
 *
 * We have not bothered to construct tuples from the data, instead the data
 * is just in Datum arrays.
 */
static Datum fc_expr_fetch_func(VacAttrStatsP fc_stats, int fc_rownum, bool *fc_isNull)
{
	int			fc_i;

	/* exprvals 和 exprnulls 已经偏移以适应适当的列 */
	fc_i = fc_rownum * fc_stats->rowstride;
	*fc_isNull = fc_stats->exprnulls[fc_i];
	return fc_stats->exprvals[fc_i];
}

/*
 * Build analyze data for a list of expressions. As this is not tied
 * directly to a relation (table or index), we have to fake some of
 * the fields in examine_expression().
 */
static AnlExprData *
fc_build_expr_data(List *fc_exprs, int fc_stattarget)
{
	int			fc_idx;
	int			fc_nexprs = list_length(fc_exprs);
	AnlExprData *fc_exprdata;
	ListCell   *fc_lc;

	fc_exprdata = (AnlExprData *) palloc0(fc_nexprs * sizeof(AnlExprData));

	fc_idx = 0;
	foreach(fc_lc, fc_exprs)
	{
		Node	   *fc_expr = (Node *) lfirst(fc_lc);
		AnlExprData *fc_thisdata = &fc_exprdata[fc_idx];

		fc_thisdata->expr = fc_expr;
		fc_thisdata->vacattrstat = fc_examine_expression(fc_expr, fc_stattarget);
		fc_idx++;
	}

	return fc_exprdata;
}

/* form an array of pg_statistic rows (per update_attstats) */
static Datum fc_serialize_expr_stats(AnlExprData *fc_exprdata, int fc_nexprs)
{
	int			fc_exprno;
	Oid			fc_typOid;
	Relation	fc_sd;

	ArrayBuildState *fc_astate = NULL;

	fc_sd = table_open(StatisticRelationId, RowExclusiveLock);

	/* lookup OID of composite type for pg_statistic */
	fc_typOid = get_rel_type_id(StatisticRelationId);
	if (!OidIsValid(fc_typOid))
		ereport(ERROR,
				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
				 errmsg("relation \"%s\" does not have a composite type",
						"pg_statistic")));

	for (fc_exprno = 0; fc_exprno < fc_nexprs; fc_exprno++)
	{
		int			fc_i,
					fc_k;
		VacAttrStats *fc_stats = fc_exprdata[fc_exprno].vacattrstat;

		Datum		fc_values[Natts_pg_statistic];
		bool		fc_nulls[Natts_pg_statistic];
		HeapTuple	fc_stup;

		if (!fc_stats->stats_valid)
		{
			fc_astate = accumArrayResult(fc_astate,
									  (Datum) 0,
									  true,
									  fc_typOid,
									  CurrentMemoryContext);
			continue;
		}

		/*
		 * 构造一个新的 pg_statistic 元组
		 */
		for (fc_i = 0; fc_i < Natts_pg_statistic; ++fc_i)
		{
			fc_nulls[fc_i] = false;
		}

		fc_values[Anum_pg_statistic_starelid - 1] = ObjectIdGetDatum(InvalidOid);
		fc_values[Anum_pg_statistic_staattnum - 1] = Int16GetDatum(InvalidAttrNumber);
		fc_values[Anum_pg_statistic_stainherit - 1] = BoolGetDatum(false);
		fc_values[Anum_pg_statistic_stanullfrac - 1] = Float4GetDatum(fc_stats->stanullfrac);
		fc_values[Anum_pg_statistic_stawidth - 1] = Int32GetDatum(fc_stats->stawidth);
		fc_values[Anum_pg_statistic_stadistinct - 1] = Float4GetDatum(fc_stats->stadistinct);
		fc_i = Anum_pg_statistic_stakind1 - 1;
		for (fc_k = 0; fc_k < STATISTIC_NUM_SLOTS; fc_k++)
		{
			fc_values[fc_i++] = Int16GetDatum(fc_stats->stakind[fc_k]); /* stakindN */
		}
		fc_i = Anum_pg_statistic_staop1 - 1;
		for (fc_k = 0; fc_k < STATISTIC_NUM_SLOTS; fc_k++)
		{
			fc_values[fc_i++] = ObjectIdGetDatum(fc_stats->staop[fc_k]);	/* staopN */
		}
		fc_i = Anum_pg_statistic_stacoll1 - 1;
		for (fc_k = 0; fc_k < STATISTIC_NUM_SLOTS; fc_k++)
		{
			fc_values[fc_i++] = ObjectIdGetDatum(fc_stats->stacoll[fc_k]);	/* stacollN */
		}
		fc_i = Anum_pg_statistic_stanumbers1 - 1;
		for (fc_k = 0; fc_k < STATISTIC_NUM_SLOTS; fc_k++)
		{
			int			fc_nnum = fc_stats->numnumbers[fc_k];

			if (fc_nnum > 0)
			{
				int			fc_n;
				Datum	   *fc_numdatums = (Datum *) palloc(fc_nnum * sizeof(Datum));
				ArrayType  *fc_arry;

				for (fc_n = 0; fc_n < fc_nnum; fc_n++)
					fc_numdatums[fc_n] = Float4GetDatum(fc_stats->stanumbers[fc_k][fc_n]);
				/* XXX 对 float4 类型知道的太多： */
				fc_arry = construct_array(fc_numdatums, fc_nnum,
									   FLOAT4OID,
									   sizeof(float4), true, TYPALIGN_INT);
				fc_values[fc_i++] = PointerGetDatum(fc_arry);	/* stanumbersN */
			}
			else
			{
				fc_nulls[fc_i] = true;
				fc_values[fc_i++] = (Datum) 0;
			}
		}
		fc_i = Anum_pg_statistic_stavalues1 - 1;
		for (fc_k = 0; fc_k < STATISTIC_NUM_SLOTS; fc_k++)
		{
			if (fc_stats->numvalues[fc_k] > 0)
			{
				ArrayType  *fc_arry;

				fc_arry = construct_array(fc_stats->stavalues[fc_k],
									   fc_stats->numvalues[fc_k],
									   fc_stats->statypid[fc_k],
									   fc_stats->statyplen[fc_k],
									   fc_stats->statypbyval[fc_k],
									   fc_stats->statypalign[fc_k]);
				fc_values[fc_i++] = PointerGetDatum(fc_arry);	/* stavaluesN */
			}
			else
			{
				fc_nulls[fc_i] = true;
				fc_values[fc_i++] = (Datum) 0;
			}
		}

		fc_stup = heap_form_tuple(RelationGetDescr(fc_sd), fc_values, fc_nulls);

		fc_astate = accumArrayResult(fc_astate,
								  heap_copy_tuple_as_datum(fc_stup, RelationGetDescr(fc_sd)),
								  false,
								  fc_typOid,
								  CurrentMemoryContext);
	}

	table_close(fc_sd, RowExclusiveLock);

	return makeArrayResult(fc_astate, CurrentMemoryContext);
}

/*
 * Loads pg_statistic record from expression statistics for expression
 * identified by the supplied index.
 */
HeapTuple statext_expressions_load(Oid fc_stxoid, bool fc_inh, int fc_idx)
{
	bool		fc_isnull;
	Datum		fc_value;
	HeapTuple	fc_htup;
	ExpandedArrayHeader *fc_eah;
	HeapTupleHeader fc_td;
	HeapTupleData fc_tmptup;
	HeapTuple	fc_tup;

	fc_htup = SearchSysCache2(STATEXTDATASTXOID,
						   ObjectIdGetDatum(fc_stxoid), BoolGetDatum(fc_inh));
	if (!HeapTupleIsValid(fc_htup))
		elog(ERROR, "cache lookup failed for statistics object %u", fc_stxoid);

	fc_value = SysCacheGetAttr(STATEXTDATASTXOID, fc_htup,
							Anum_pg_statistic_ext_data_stxdexpr, &fc_isnull);
	if (fc_isnull)
		elog(ERROR,
			 "requested statistics kind \"%c\" is not yet built for statistics object %u",
			 STATS_EXT_EXPRESSIONS, fc_stxoid);

	fc_eah = DatumGetExpandedArray(fc_value);

	deconstruct_expanded_array(fc_eah);

	fc_td = DatumGetHeapTupleHeader(fc_eah->dvalues[fc_idx]);

	/* 构建一个临时 HeapTuple 控制结构 */
	fc_tmptup.t_len = HeapTupleHeaderGetDatumLength(fc_td);
	ItemPointerSetInvalid(&(fc_tmptup.t_self));
	fc_tmptup.t_tableOid = InvalidOid;
	fc_tmptup.t_data = fc_td;

	fc_tup = heap_copytuple(&fc_tmptup);

	ReleaseSysCache(fc_htup);

	return fc_tup;
}

/*
 * Evaluate the expressions, so that we can use the results to build
 * all the requested statistics types. This matters especially for
 * expensive expressions, of course.
 */
static StatsBuildData *
fc_make_build_data(Relation fc_rel, StatExtEntry *fc_stat, int fc_numrows, HeapTuple *fc_rows,
				VacAttrStats **fc_stats, int fc_stattarget)
{
	/* evaluated expressions */
	StatsBuildData *fc_result;
	char	   *fc_ptr;
	Size		fc_len;

	int			fc_i;
	int			fc_k;
	int			fc_idx;
	TupleTableSlot *fc_slot;
	EState	   *fc_estate;
	ExprContext *fc_econtext;
	List	   *fc_exprstates = NIL;
	int			fc_nkeys = bms_num_members(fc_stat->columns) + list_length(fc_stat->exprs);
	ListCell   *fc_lc;

	/* allocate everything as a single chunk, so we can free it easily */
	fc_len = MAXALIGN(sizeof(StatsBuildData));
	fc_len += MAXALIGN(sizeof(AttrNumber) * fc_nkeys);	/* attnums */
	fc_len += MAXALIGN(sizeof(VacAttrStats *) * fc_nkeys);	/* stats */

	/* values */
	fc_len += MAXALIGN(sizeof(Datum *) * fc_nkeys);
	fc_len += fc_nkeys * MAXALIGN(sizeof(Datum) * fc_numrows);

	/* nulls */
	fc_len += MAXALIGN(sizeof(bool *) * fc_nkeys);
	fc_len += fc_nkeys * MAXALIGN(sizeof(bool) * fc_numrows);

	fc_ptr = palloc(fc_len);

	/* set the pointers */
	fc_result = (StatsBuildData *) fc_ptr;
	fc_ptr += MAXALIGN(sizeof(StatsBuildData));

	/* attnums */
	fc_result->attnums = (AttrNumber *) fc_ptr;
	fc_ptr += MAXALIGN(sizeof(AttrNumber) * fc_nkeys);

	/* stats */
	fc_result->stats = (VacAttrStats **) fc_ptr;
	fc_ptr += MAXALIGN(sizeof(VacAttrStats *) * fc_nkeys);

	/* values */
	fc_result->values = (Datum **) fc_ptr;
	fc_ptr += MAXALIGN(sizeof(Datum *) * fc_nkeys);

	/* nulls */
	fc_result->nulls = (bool **) fc_ptr;
	fc_ptr += MAXALIGN(sizeof(bool *) * fc_nkeys);

	for (fc_i = 0; fc_i < fc_nkeys; fc_i++)
	{
		fc_result->values[fc_i] = (Datum *) fc_ptr;
		fc_ptr += MAXALIGN(sizeof(Datum) * fc_numrows);

		fc_result->nulls[fc_i] = (bool *) fc_ptr;
		fc_ptr += MAXALIGN(sizeof(bool) * fc_numrows);
	}

	Assert((fc_ptr - (char *) fc_result) == fc_len);

	/* we have it allocated, so let's fill the values */
	fc_result->nattnums = fc_nkeys;
	fc_result->numrows = fc_numrows;

	/* fill the attribute info - first attributes, then expressions */
	fc_idx = 0;
	fc_k = -1;
	while ((fc_k = bms_next_member(fc_stat->columns, fc_k)) >= 0)
	{
		fc_result->attnums[fc_idx] = fc_k;
		fc_result->stats[fc_idx] = fc_stats[fc_idx];

		fc_idx++;
	}

	fc_k = -1;
	foreach(fc_lc, fc_stat->exprs)
	{
		Node	   *fc_expr = (Node *) lfirst(fc_lc);

		fc_result->attnums[fc_idx] = fc_k;
		fc_result->stats[fc_idx] = fc_examine_expression(fc_expr, fc_stattarget);

		fc_idx++;
		fc_k--;
	}

	/* first extract values for all the regular attributes */
	for (fc_i = 0; fc_i < fc_numrows; fc_i++)
	{
		fc_idx = 0;
		fc_k = -1;
		while ((fc_k = bms_next_member(fc_stat->columns, fc_k)) >= 0)
		{
			fc_result->values[fc_idx][fc_i] = heap_getattr(fc_rows[fc_i], fc_k,
												  fc_result->stats[fc_idx]->tupDesc,
												  &fc_result->nulls[fc_idx][fc_i]);

			fc_idx++;
		}
	}

	/* Need an EState for evaluation expressions. */
	fc_estate = CreateExecutorState();
	fc_econtext = GetPerTupleExprContext(fc_estate);

	/* 还需要一个槽来保存当前的堆元组 */  
	fc_slot = MakeSingleTupleTableSlot(RelationGetDescr(fc_rel),
									&TTSOpsHeapTuple);

	/* 安排econtext的扫描元组为待测试的元组 */
	fc_econtext->ecxt_scantuple = fc_slot;

	/* Set up expression evaluation state */
	fc_exprstates = ExecPrepareExprList(fc_stat->exprs, fc_estate);

	for (fc_i = 0; fc_i < fc_numrows; fc_i++)
	{
		/*
		 * Reset the per-tuple context each time, to reclaim any cruft left
		 * behind by evaluating the statistics object expressions.
		 */
		ResetExprContext(fc_econtext);

		/* Set up for expression evaluation */
		ExecStoreHeapTuple(fc_rows[fc_i], fc_slot, false);

		fc_idx = bms_num_members(fc_stat->columns);
		foreach(fc_lc, fc_exprstates)
		{
			Datum		fc_datum;
			bool		fc_isnull;
			ExprState  *fc_exprstate = (ExprState *) lfirst(fc_lc);

			/*
			 * XXX This probably leaks memory. Maybe we should use
			 * ExecEvalExprSwitchContext but then we need to copy the result
			 * somewhere else.
			 */
			fc_datum = ExecEvalExpr(fc_exprstate,
								 GetPerTupleExprContext(fc_estate),
								 &fc_isnull);
			if (fc_isnull)
			{
				fc_result->values[fc_idx][fc_i] = (Datum) 0;
				fc_result->nulls[fc_idx][fc_i] = true;
			}
			else
			{
				fc_result->values[fc_idx][fc_i] = (Datum) fc_datum;
				fc_result->nulls[fc_idx][fc_i] = false;
			}

			fc_idx++;
		}
	}

	ExecDropSingleTupleTableSlot(fc_slot);
	FreeExecutorState(fc_estate);

	return fc_result;
}
